package tree

// Z 字形打印二叉树

func ZigzagLevelOrder(root *Node) [][]int {
	result := make([][]int, 0)
	if root == nil {
		return result
	}

	queue := make([]*Node, 0)
	queue = append(queue, root)
	toggle := false

	for len(queue) > 0 {
		list := make([]int, 0)
		//遍历当前层元素，并添加下一层元素
		l := len(queue)
		for i := 0; i < l; i++ {
			levelNode := queue[0]
			queue = queue[1:]
			list = append(list, levelNode.Val)
			if levelNode.Left != nil {
				queue = append(queue, levelNode.Left)
			}

			if levelNode.Right != nil {
				queue = append(queue, levelNode.Right)
			}
		}
		if toggle {
			//翻转本层的节点
			reverseLevel(list)
		}

		result = append(result, list)
		toggle = !toggle
	}

	return result

}

func reverseLevel(nums []int) {
	for i := 0; i < len(nums)/2; i++ {
		nums[i], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[i]
	}
}
